' ==================================================== ' Small Basic LP Cheapest Recipe ' ' This version: attempt to adapt version 1.0 to the case of CALCULATION ' OF CHEAPEST RECIPE ' ' Version 3.0 - Date 11 January 2023 ' > implements an example by David Lippman & Melonie Rasmussen ' > The method applied is described here: ' > https://www.zweigmedia.com/tutsM/tutSimplex.php?lang=en&ed=7 ' ' http://smallbasic.com/program/?TJTX409.000 ' ' ==================================================== ' LINEAR PROGRAMMING TECHNIQUE ' From an excercise by David Lippman ( ) & Melonie Rasmussen ' The problem was exemplified here ' https://math.libretexts.org/Courses/Highline_College/Math_111%3A_College_Algebra/03%3A_Linear_Programming/3.05%3A_Applications_of__Linear_Programming ' The algorithm is described here ' https://math.libretexts.org/Courses/Highline_College/Math_111%3A_College_Algebra/03%3A_Linear_Programming/3.04%3A_Simplex_Method ' The method applied is described here: ' https://www.zweigmedia.com/tutsM/tutSimplex.php?lang=en&ed=7 ' ' This program is based on the excellent explanations available in: ' Explanations from IMSE Concept Library | Laurel Nichols & Gina Christofaro | Spring 2015 ' https://www.imse.iastate.edu/files/2015/08/Explanation-of-Simplex-Method.docx ' but solving a more complex scenario required a thprough reding of: ' https://www.zweigmedia.com/tutsM/tutSimplex.php?lang=en&ed=7 ' ' Ported in Small Basic by Cesare Brizio ' (www.cesarebrizio.it) ' --------------------------------------------------------- ' THE CHEAPEST RECIPE PROBLEM ' --------------------------------------------------------- ' Since the end of the 1960's, my father was a pioneer in the application of ' computers to the automation of animal feed factories. ' With his undisputed intelligence, he most probably designed his algorithms ' from scratch. But it's a possibility that he studied linear algorithms. ' (https://en.wikipedia.org/wiki/Linear_programming) ' in which linear equality and linear inequality constraints become metaphors ' of real-world problems. In actuality, the definition of a "closed feasible ' region' of a problem is performed on geometrical terms. ' The Simplex algorithm was devised by George Dantzig in 1947, so it's a ' candidate influencer of my father's methods. ' ----------------------------------------------------------------------------------------- ' In this case, that closely resembles the problems solved by my father, ' the target is to provide the cheapest possible mixture of ingredients, ' that grants the presence of a given proportion of substances. ' Base ingredients have different prices and contain the required substances. ' The proportions of substances present in each ingredient differ from both ' those required for the final mixture, and those of other ingredients. ' ==================================================== CRLF = Text.GetCharacter(13) + Text.GetCharacter(10) Message = Message + "This program is just an algorithm demonstrator."+CRLF Message = Message + "Please see comments in the heading of the source"+CRLF Message = Message + "code for more details."+CRLF Message = Message + "Values are hard-coded and no user interface is"+CRLF Message = Message + "provided."+CRLF Message = Message + "An effective application should be parametric"+CRLF Message = Message + "and include provisions to design the objective"+CRLF Message = Message + "functions and the constraints. Plus, in a"+CRLF Message = Message + "real-world scenario, it would be advisable"+CRLF Message = Message + "to store in a database all the data such as"+CRLF Message = Message + "the recipes and the nutritional constraints."+CRLF Message = Message + "--------------------------------------------"+CRLF Message = Message + "A minimal effort has been put in using arrays"+CRLF Message = Message + "to store the values needed for the problem and"+CRLF Message = Message + "its solution. Those arrays may simulate simple"+CRLF Message = Message + "database tables and inspire the design of an"+CRLF Message = Message + "actual RDBMS for nutritional constraints,"+CRLF Message = Message + "ingredient composition and actual recipes."+CRLF Message = Message + "--------------------------------------------"+CRLF Message = Message + "In other words, the design of the Simplex"+CRLF Message = Message + "Tableau should be entrely automated, with as"+CRLF Message = Message + "many colums as needed to cover the nutritional"+CRLF Message = Message + "constraints of any recipe and the composition"+CRLF Message = Message + "of each ingredient."+CRLF Message = Message + "Feel free to improve this sketch as needed!"+CRLF 'GraphicsWindow.ShowMessage(Message,"LINEAR PROGRAMMING EXAMPLE") Message = "============================================"+CRLF Message = "================> EXERCISE <================"+CRLF Message = "============================================"+CRLF Message = "A company is creating a meal replacement bar."+CRLF Message = Message + "They plan to incorporate peanut butter," Message = Message + "oats, and dried cranberries asthe primary ingredients." Message = Message + "The nutritional content of 10 grams of each is listed " Message = Message + "below, along with the cost, in cents, of each ingredient." Message = Message + "Find the amount of each ingredient they should use to" Message = Message + "minimize the cost of producing a barcontaining a " Message = Message + "minimum of 15g of each ingredient, at least 10g" Message = Message + "of protein and at most 14g of fat."+CRLF Message = Message + ""+CRLF Message = Message + "Current implementation has no user interface, you are" Message = Message + "welcome to improve it anytime. Values are hard-coded into" Message = Message + "variables and you can change them by intervening" Message = Message + "on the source code."+CRLF Message = Message + ""+CRLF Message = Message + "CONTENTS OF 10 GRAMS OF INGREDIENT"+CRLF Message = Message + "----------------------------------"+CRLF Message = Message + "PEANUT BUTTER, Proteins 2.5g (Ppb) - Fat 5g(Fpb)"+CRLF Message = Message + "OATS, Proteins 1.7g (Po) - Fat 0.7g (Fo)"+CRLF Message = Message + "CRANBERRIES, Proteins 0g (Pc)- Fat 0.1g (Fc)"+CRLF Message = Message + ""+CRLF Message = Message + "COST OF 10 GRAMS OF INGREDIENT"+CRLF Message = Message + "----------------------------------"+CRLF Message = Message + "PEANUT BUTTER, 6 cent (Cp)"+CRLF Message = Message + "OATS, 1 cent (Co)"+CRLF Message = Message + "CRANBERRIES, 2 cent (Cc)"+CRLF Message = Message + ""+CRLF Message = Message + "=============================================="+CRLF Message = Message + " FORMAL DESCRIPTION OF THE PROBLEM"+CRLF Message = Message + "=============================================="+CRLF Message = Message + " MINIMIZE COST = 6Cp + 1Co + 2Cc"+CRLF Message = Message + " Subject to:"+CRLF Message = Message + " 2.5Ppb + 1.7Po + 0Pc >= 10 (at least 10g of protein)"+CRLF Message = Message + " 5Ppb + 0.7Po + 0.1Pc <= 14 (no more than 14g of fat)"+CRLF Message = Message + " Ppb ≥ 1.5 (at least 15g of Peanut Butter)"+CRLF Message = Message + " Po ≥ 1.5 (at least 15g of Oats)"+CRLF Message = Message + " Pc ≥ 1.5 (at least 15g of Cranberries)"+CRLF Message = Message + "=============================================="+CRLF Message = Message + " SOLUTION"+CRLF Message = Message + "=============================================="+CRLF Message = Message + "COST = 15.6765" +CRLF Message = Message + "Ppb = 1.5 (15 grams)" +CRLF Message = Message + "Po = 3.67647 (36,8 grams)" +CRLF Message = Message + "Pc = 1.5 (15 grams)"+CRLF Message = Message + ""+CRLF Message = Message + "Interpreting that result, the minimum cost to produce Message = Message + "the bar will be about 15 cents, by using 15 grams of" Message = Message + "peanut butter, 36.8 grams of oats, and 15 grams of " Message = Message + "dried cranberries. Verifying our conditions, we can" Message = Message + "see that our recipe contains at least 15g of each" Message = Message + "ingredient."+CRLF Message = Message + "The protein content will be around 10g"+CRLF Message = Message + "(2.5*1.5)+(1.7*3.68)+(0*1.5)"+CRLF Message = Message + "The fat content will be around 10.15g"+CRLF Message = Message + "(5*1.5)+(0.7*3.68)+(0.1*1.5)"+CRLF Message = Message + "" 'GraphicsWindow.ShowMessage(Message,"LINEAR PROGRAMMING EXAMPLE") '============================================== ' CONSTRAINTS ' One row per constraint ' One column per ingredient ' Last columns are the condition sign ' (all the condition must be equal, so a >= ' condition can be changed to <= by ' multiplying it by -1) and the last column ' is the required value. Indexing is ' Constraint[Constraint][component value] ' Constraint[Constraint][4] contains the value of the constraint '============================================== NUM_CONSTRAINTS = 5 '=========================================== ' CONSTRAINT 1 is "PROTEIN CONTENT" ' 2.5Ppb + 1.7Po + 0Pc >= 10 (at least 10g of protein) '=========================================== Constraint_description[1] = "MINIMUM GRAMS OF PROTEIN REQUIRED " Constraint_sign[1] = -1 ' More-than-or-equal-to inequality requires NEGATIVE slack variable Constraint[1][1] = 2.5 'Peanut Butter Constraint[1][2] = 1.7 'Oats Constraint[1][3] = 0 'Cranberries Constraint[1][4] = 10 '=========================================== ' CONSTRAINT 2 is "FAT CONTENT" ' 5Ppb + 0.7Po + 0.1Pc <= 14 (no more than 14g of fat)" '=========================================== Constraint_description[2] = "MAXIMUM GRAMS OF FAT REQUIRED " Constraint_sign[2] = 1 ' Less-than-or-equal-to inequality requires POSITIVE slack variable Constraint[2][1] = 5 'Peanut Butter Constraint[2][2] = 0.7 'Oats Constraint[2][3] = 0.1 'Cranberries Constraint[2][4] = 14 '=========================================== ' CONSTRAINT 3 is "AT LEAST 15g OF PEANUT BUTTER" ' 1Ppb + 0Po + 0Pc >= 1.5 (at least 15g of Peanut Butter)" '=========================================== Constraint_sign[3] = -1 ' More-than-or-equal-to inequality requires NEGATIVE slack variable Constraint[3][1] = 1 'Peanut Butter Constraint[3][2] = 0 'Oats Constraint[3][3] = 0 'Cranberries Constraint[3][4] = 1.5 '=========================================== ' CONSTRAINT 4 is "AT LEAST 15g OF OATS" ' 0Ppb + 1Po + 0Pc >= 1.5 (at least 15g of Oats)" '=========================================== Constraint_sign[4] = -1 ' More-than-or-equal-to inequality requires NEGATIVE slack variable Constraint[4][1] = 0 'Peanut Butter Constraint[4][2] = 1 'Oats Constraint[4][3] = 0 'Cranberries Constraint[4][4] = 1.5 '============================================== ' CONSTRAINT 5 is "AT LEAST 15g OF DRIED CRANBERRIES" ' 0Ppb + 0Po + 1Pc >= 1.5 (at least 15g of Cranberries)" '==========================================)==== Constraint_sign[5] = -1 ' More-than-or-equal-to inequality requires NEGATIVE slack variable Constraint[5][1] = 0 'Peanut Butter Constraint[5][2] = 0 'Oats Constraint[5][3] = 1 'Cranberries Constraint[5][4] = 1.5 '---------------------------------------------------- ' OBJECTIVE FUNCTION ' ' MINIMIZE COST = 6Cp + 1Co + 2Cc ' ' translated into ' ' MAXIMIZE -COST = -6Cp - 1Co - 2Cc ' ' Ingredients are the three variables in ' the constraints and in the objective ' function '---------------------------------------------------- OBJECTIVE_FUNCTION_SIGN = 1 ' will be used more under '---------------------------------------------------- ' NAMES OF INGREDIENTS '---------------------------------------------------- NUM_INGREDIENTS = 3 ING_NAMES[1] = "PEANUT BUTTER" ING_NAMES[2] = "OATS" ING_NAMES[3] = "CRANBERRIES" '---------------------------------------------------- ' COST OF INGREDIENTS ' COST is the OBJECTIVE FUNCTION to ' minimize '---------------------------------------------------- ING_COST[1] = 6 ING_COST[2] = 1 ING_COST[3] = 2 '======================================== ' Four arrays that will help debug and result visualization '======================================== Serving_Size = 10 ' grams per "serving" - an arbitrary unit on wich the quantity ' of nutrients (proteins and fat) is based, e.g. "0,7 grams on 10 grams" COLUMN_FULL_NAME[1] = "Grams per bar, PEANUT BUTTER " COLUMN_FULL_NAME[2] = "Grams per bar, OATS " COLUMN_FULL_NAME[3] = "Grams per bar, DRIED CRANBERRIES " COLUMN_FULL_NAME[4] = "SLACK VARIABLE 1" COLUMN_FULL_NAME[5] = "SLACK VARIABLE 2" COLUMN_FULL_NAME[6] = "SLACK VARIABLE 3" COLUMN_FULL_NAME[7] = "SLACK VARIABLE 4" COLUMN_FULL_NAME[8] = "SLACK VARIABLE 5" COLUMN_FULL_NAME[9] = "COST PER BAR (cents) " COLUMN_FULL_NAME[10] = "BETA COLUMN " SHOW_RESULT[1] = "True" SHOW_RESULT[2] = "True" SHOW_RESULT[3] = "True" SHOW_RESULT[4] = "False" SHOW_RESULT[5] = "False" SHOW_RESULT[6] = "False" SHOW_RESULT[7] = "False" SHOW_RESULT[8] = "False" SHOW_RESULT[9] = "True" SHOW_RESULT[10] = "False" RESULT_MULTIPLIER[1] = Serving_Size 'result will be the number of 10 grams servings RESULT_MULTIPLIER[2] = Serving_Size 'result will be the number of 10 grams servings RESULT_MULTIPLIER[3] = Serving_Size 'result will be the number of 10 grams servings RESULT_MULTIPLIER[4] = 1 RESULT_MULTIPLIER[5] = 1 RESULT_MULTIPLIER[6] = 1 RESULT_MULTIPLIER[7] = 1 RESULT_MULTIPLIER[8] = 1 RESULT_MULTIPLIER[9] = -1 'result will be negative due to the initial sign reversal RESULT_MULTIPLIER[10] = 1 COLUMN_NAME[1] = " X" ' PEANUT BUTTER" COLUMN_NAME[2] = " Y" ' OATS" COLUMN_NAME[3] = " Z" ' CRANBERRIES" COLUMN_NAME[4] = "S1" ' "SLACK VARIABLE 1" COLUMN_NAME[5] = "S2" ' "SLACK VARIABLE 2" COLUMN_NAME[6] = "S3" ' "SLACK VARIABLE 3" COLUMN_NAME[7] = "S4" ' "SLACK VARIABLE 4" COLUMN_NAME[8] = "S5" ' "SLACK VARIABLE 5" COLUMN_NAME[9] = " C" ' "OBJECTIVE FUNCTION VALUE (COST)" COLUMN_NAME[10] = "BETA COLUMN" '======================================== ' STANDARD FORM '======================================== '(1) must be a maximization problem, '(2) all linear constraints must be in a less-than-or-equal-to inequality, '(3) all variables are non-negative. ' ' To transform a minimization linear program model into ' a maximization linear program model, simply multiply both ' the left and the right sides of the objective function by -1. ' MINIMIZE COST = 6Cp + 1Co + 2Cc ' becomes ' MAXIMIZE COST = -6Cp - 1Co - 2Cc ' ' Transforming linear constraints from a greater-than-or-equal-to inequality ' to a less-than-or-equal-to inequality can be done similarly as what was done ' to the objective function. By multiplying by -1 on both sides, the inequality can ' be changed to less-than-or-equal-to. '========================================= 'Constraint_sign[I] will be used For the slack variable '========================================= '======================================== ' DETERMINE SLACK VARIABLES '======================================== ' Slack variables are additional variables that are introduced into the linear ' constraints of a linear program to transform them from inequality constraints ' to equality constraints. If the model is in standard form, the slack variables ' will always have a +1 coefficient. Slack variables are needed in the constraints ' to transform them into solvable equalities with one definite answer. ' ' THE SLACK VARIABLES WILL BE ADDED DURING ' THE CREATION OF THE TABLEAU '======================================== ' BUILD THE SIMPLEX TABLEAU '======================================== ' See http://pages.intnet.mu/cueboy/education/notes/algebra/simplex.htm#Example%201 ' There is a tableau row for each condition, plus one tableau row ' for quantifying the objective function to be maximized/minimized ' In each row, there is one column for each variable (in our case, ' for each ingredient) plus the columns for "slack variables", whose number ' is equal to the number of constraints. ' The rightmost column is used to store the target values for the conditions ' defined in each line ' The last line contains the values of the objective function to maximize or minimize ' '--------------------------------------- ' As many rows, as conditions +1 '--------------------------------------- Vertical_Size_Tableau = NUM_CONSTRAINTS+1 '-------------------------------------------------------------- ' As many columns, as double the ingredients +2 ' (one slack variables per constraint and one total column are needed) '--------------------------------------------------------------- Horizontal_Size_Tableau = (NUM_INGREDIENTS+NUM_CONSTRAINTS)+2 ' initialize all tableau cells at 0 For I = 1 To Vertical_Size_Tableau For J = 1 To Horizontal_Size_Tableau Tableau[I][J]=0.000 EndFor EndFor '------------------------------------------------------- ' Fill the top left part of the simplex tableau ' One condition per row ' One ingredient per column (conditions are ' defined as proportions of ingredients) '------------------------------------------------------- For I = 1 To NUM_CONSTRAINTS For J = 1 To NUM_INGREDIENTS Tableau[I][J]=Constraint[I][J] EndFor EndFor ' DEBUG 'ShowSimplexTableau() 'TextWindow.WriteLine("Above, before putting slack variables in the tableau") 'TextWindow.Read() '------------------------------------------------------- ' PUT SLACK VARIABLES IN THE TABLEAU '------------------------------------------------------- ' put the slack variables as a diagonal line in front of the conditions For I = 1 To NUM_CONSTRAINTS For J = (NUM_INGREDIENTS+1) To Horizontal_Size_Tableau-1 Curr_Column = J-NUM_INGREDIENTS If I = Curr_Column Then Tableau[I][J]= Constraint_sign[I] EndIf EndFor EndFor '---------------------------------------------------------------------------- ' Fill the last slack variable at the penultimate column ' of the last row with the objective function sign '---------------------------------------------------------------------------- Tableau[Vertical_Size_Tableau][Horizontal_Size_Tableau-1] = OBJECTIVE_FUNCTION_SIGN ' DEBUG 'ShowSimplexTableau() 'TextWindow.WriteLine("Above, before putting constraint values in the tableau") 'TextWindow.Read() '------------------------------------------------------- ' PUT CONSTRAINT VALUES IN THE LAST ' COLUMN OF THE TABLEAU '------------------------------------------------------- ' Fill the last column of the simplex tableau For I = 1 To NUM_CONSTRAINTS Tableau[I][Horizontal_Size_Tableau] = Constraint[I][4] EndFor ' DEBUG 'ShowSimplexTableau() 'TextWindow.WriteLine("Above, before putting objective functions coefficients in the tableau") 'TextWindow.Read() '------------------------------------------------------- ' PREPARE A VECTOR TO ' COLUMN OF THE TABLEAU '------------------------------------------------------- For I = 1 To Horizontal_Size_Tableau Already_Pivoted[I] = "False" EndFor '------------------------------------------------------- ' PUT THE OBJECTIVE FUNCTIONS ' COEFFICIENTS IN THE LAST LINE ' OF THE TABLEAU. ' THE VALUES SHOULD BE MULTIPLIED BY ' -1 '------------------------------------------------------- ' Fill with COEFFICIENTS the last line of the simplex tableau For I = 1 To NUM_INGREDIENTS Tableau[NUM_CONSTRAINTS+1][I] = ING_COST[I] EndFor '====================================================== ' TABLEAU STRUCTURE '====================================================== 'Column Column Column Column Column Column Column ' 1 2 3 4 5 6 7 8 9 10 ' ' Peanut Oats Cran- S1 S2 S3 S4 S5 Z B ' Butter berries ' ' ======================================================================= ' ADD STARS ' ------------------------------------------------------- ' star all rows whose decision variables are negative to indicate that the current solution is not feasible ' the stars will be used to identify the PIVOT COLUMN in Phase 1 ' ======================================================================= For I = 1 to NUM_CONSTRAINTS+1 If Constraint_sign[I] = -1 Then STARRED[I] ="*" ' it is STARRED because it's NEGATIVE Else STARRED[I] =" " EndIf EndFor '======================================== '======================================== '======================================== ' PHASE 1 - GET RID OF THE STARS '======================================== '======================================== '======================================== '======================================== ' WHILE loops in Small basic are notoriously unreliable ' as any variable-based WHILE condition is checked ' only at the beginning of the loop. 'Reluctantly, I resort to a GoTo '======================================== TABLEAU_NUMBER = 1 BEGIN_LOOP: 'DEBUG ShowSimplexTableau() TextWindow.Read() ' --------------------------------------------------------------------------------------------------- ' The rule for the selecting a pivot column is this: Look at all the entries in the first ' starred row, excluding the last entry on the right (in the "answers" column). ' From these, choose the positive number with the largest magnitude; its column ' is the pivot column. If there are two or more candidates, choose any one. If there ' are no positive numbers to choose, that indicates that the feasible region is empty, ' and so the LP problem has no solution. ' --------------------------------------------------------------------------------------------------- ' CHOOSE PIVOT COLUMN ' by anlyzing the TOP STARRED row ' CHOOSE THE COLUMN WITH THE MOST POSITIVE VALUE ' =============================================== Most_Positive_Value = -9999 ' self-explanatory Pivot_column = 0 ' self-explanatory FIRST_STARRED_ROW = 0 ' =============================================== ' FIND TOPMOST STARRED ROW ' =============================================== For Constr = NUM_CONSTRAINTS To 1 Step -1 If STARRED[Constr] = "*" Then FIRST_STARRED_ROW = Constr EndIf EndFor If FIRST_STARRED_ROW = 0 Then Goto EXIT_LOOP EndIf For i=1 To Horizontal_Size_Tableau-1 If Tableau[FIRST_STARRED_ROW][i] <> 0 Then ' The pivot column is the one with the most positive non-zero value ' =============================================== ' CHOOSE THE COLUMN WITH THE MOST POSITIVE VALUE ' =============================================== If Tableau[FIRST_STARRED_ROW][i] > Most_Positive_Value And Already_Pivoted[I] = "False" Then Most_Positive_Value = Tableau[FIRST_STARRED_ROW][i] ' Until proved otherwise, this is the most positive (=pivot) column Pivot_column = i EndIf EndIf EndFor ' -------------------------------------------------------------------------------------- ' The algorithm should avoid processing a column twice. ' This variable was set as a security device and most probably is useless ' -------------------------------------------------------------------------------------- Already_Pivoted[Pivot_column] = "True" ' DEBUG 'TextWindow.WriteLine("Pivot column chosen - "+Pivot_column) 'TextWindow.Read() Least_Non_Negative_Ratio = 99999999999999 ' self-explanatory '====================================== ' CHOOSE PIVOT ROW ' by analyzing the last column '====================================== Pivot_row = 0 ' self-explanatory For I = 1 To NUM_CONSTRAINTS If Tableau[i][Pivot_column] > 0 Then If Tableau[i][Horizontal_Size_Tableau] / Tableau[i][Pivot_column] < Least_Non_Negative_Ratio Then Least_Non_Negative_Ratio = Tableau[i][Horizontal_Size_Tableau] / Tableau[i][Pivot_column] ' Until proved otherwise, this is the least non negative ratio (=pivot) row Pivot_row = i EndIf EndIf EndFor ' -------------------------------------------------------------------------------------- ' REMOVE THE STAR FROM THE PIVOTED ROW ' -------------------------------------------------------------------------------------- STARRED[Pivot_row] = " " '====================================== ' The PIVOT ELEMENT is at the intersection of ' PIVOT ROW and PIVOT COLUMN ' Make 0 all the numbers above or below the pivot ' element by using basic row operations '====================================== PIVOT_ELEMENT_VALUE = Tableau[Pivot_row][Pivot_column] RECIPROCAL_P_E_V = (1 / PIVOT_ELEMENT_VALUE) ' DEBUG 'TextWindow.WriteLine("Pivot row chosen - "+Pivot_row+" - Press any key") 'TextWindow.WriteLine("Pivot element value = "+PIVOT_ELEMENT_VALUE+" - Press any key") 'TextWindow.Read() '----------------------> SET TO ZERO ALL THE VALUES IN THE PIVOT COLUMN '----------------------> EXCEPT THE PIVOT ELEMENT For update_row = 1 To Vertical_Size_Tableau If update_row <> Pivot_row Then ' The previous values of the pivot column now being overwritten are needed ' more under OLD_VALUE_PIVOT_COLUMN[update_row] = Tableau[update_row][Pivot_column] Tableau[update_row][Pivot_column] = 0 EndIf EndFor '----------------------> UPDATE THE ROW For update_column = 1 To Horizontal_Size_Tableau Tableau[Pivot_row][update_column] = Tableau[Pivot_row][update_column] * RECIPROCAL_P_E_V EndFor For update_row = 1 To Vertical_Size_Tableau For update_column = 1 To Horizontal_Size_Tableau ' Here for any cell in the Tableau If update_column <> Pivot_column Then ' Here for any cell in the Tableau outside the PIVOT COLUMN If update_row <> Pivot_row Then ' Here for any non-zero cell in the Tableau outside the PIVOT COLUMN and the PIVOT ROW ' =================================================================== ' Explanations from IMSE Concept Library | Laurel Nichols & Gina Christofaro | Spring 2015 ' ------------------------------------------------------------------------------------------------------------------ ' In order to keep the tableau equivalent, the other variables not contained in the pivot column ' or pivot row must be calculated by using the new pivot values. For each new value, multiply ' the negative of the value in the old pivot column by the value in the new pivot row that ' corresponds to the value being calculated. Then add this to the old value from the old tableau ' to produce the new value for the new tableau. ' =================================================================== ' just for clarity, I store the current cell value in a variable Curr_cell_value = Tableau[update_row][update_column] ' the new values from the pivot row are readily available. I select the one corrresponding ' to the current column Value_new_pivot_row = Tableau[Pivot_row][update_column] ' the old values from the pivot column were saved beforehand. I select the one corrresponding ' to the current row, and change its sign Neg_value_old_pivot_column = OLD_VALUE_PIVOT_COLUMN[update_row] * -1 ' now the value for the new tableau cell can be assigned Tableau[update_row][update_column]=(Neg_value_old_pivot_column * Value_new_pivot_row) + Curr_cell_value EndIf EndIf EndFor EndFor TABLEAU_NUMBER = TABLEAU_NUMBER + 1 Goto BEGIN_LOOP EXIT_LOOP: TextWindow.WriteLine(" ") TextWindow.WriteLine(" PHASE 1 COMPLETED - NO MORE STARRED ROWS") TextWindow.Read() '======================================== '======================================== '======================================== ' PHASE 2 - COMPLETE OPTIMIZATION '======================================== '======================================== '======================================== '======================================== ' WHILE loops in Small basic are notoriously unreliable ' as any variable-based WHILE condition is checked ' only at the beginning of the loop. 'Reluctantly, I resort to a GoTo '======================================== BEGIN_SECOND_LOOP: 'DEBUG ShowSimplexTableau() TextWindow.Read() '---------- Pseudo-boolean for negative values in the bottom row Neg_Val_Bottom_Line = "FALSE" '====================================== ' CHECK IF THE BOTTOM ROW CONTAINS ' NEGATIVE VALUES, IF NO NEGATIVE VALUE ' EXISTS THE TABLEAU IS OPTIMIZED '====================================== For i=1 To Horizontal_Size_Tableau - 1 If Tableau[Vertical_Size_Tableau][i] < 0 Then Neg_Val_Bottom_Line = "TRUE" EndIf EndFor ' Loop is terminated as soon as no negative values can be found in the ' left part of the bottom row If Neg_Val_Bottom_Line = "FALSE" Then Goto EXIT_SECOND_LOOP EndIf ' DEBUG 'TextWindow.WriteLine("Neg_Val_Bottom_Line - "+ Neg_Val_Bottom_Line) 'TextWindow.Read() '====================================== ' CHOOSE PIVOT COLUMN ' by anlyzing the bottom row ' CHOOSE THE COLUMN WITH THE MOST NEGATIVE VALUE '====================================== Most_Negative_Value = 0 ' self-explanatory Pivot_column = 0 ' self-explanatory For i=1 To Horizontal_Size_Tableau-1 If Tableau[Vertical_Size_Tableau][i] < 0 Then ' The pivot column is the one with the most negative value If Tableau[Vertical_Size_Tableau][i] < Most_Negative_Value Then Most_Negative_Value = Tableau[Vertical_Size_Tableau][i] ' Until proved otherwise, this is the most negative (=pivot) column Pivot_column = i EndIf EndIf EndFor ' -------------------------------------------------------------------------------------- ' The algorithm should avoid processing a column twice. ' This variable was set as a security device and most probably is useless ' -------------------------------------------------------------------------------------- Already_Pivoted[Pivot_column] = "True" ' DEBUG ' TextWindow.WriteLine("Pivot column chosen - "+Pivot_column) ' TextWindow.Read() Least_Non_Negative_Ratio = 99999999999999 ' self-explanatory '====================================== ' CHOOSE PIVOT ROW ' by analyzing the last column '====================================== Pivot_row = 0 ' self-explanatory For I = 1 To NUM_CONSTRAINTS If Tableau[i][Pivot_column] > 0 Then If Tableau[i][Horizontal_Size_Tableau] / Tableau[i][Pivot_column] < Least_Non_Negative_Ratio Then Least_Non_Negative_Ratio = Tableau[i][Horizontal_Size_Tableau] / Tableau[i][Pivot_column] ' Until proved otherwise, this is the least non negative ratio (=pivot) row Pivot_row = i EndIf EndIf EndFor '====================================== ' The PIVOT ELEMENT is at the intersection of ' PIVOT ROW and PIVOT COLUMN ' Make 0 all the numbers above or below the pivot ' element by using basic row operations '====================================== PIVOT_ELEMENT_VALUE = Tableau[Pivot_row][Pivot_column] RECIPROCAL_P_E_V = (1 / PIVOT_ELEMENT_VALUE) ' DEBUG 'TextWindow.WriteLine("Pivot row chosen - "+Pivot_row+" - Press any key") 'TextWindow.WriteLine("Pivot element value = "+PIVOT_ELEMENT_VALUE+" - Press any key") 'TextWindow.Read() '----------------------> SET TO ZERO ALL THE VALUES IN THE PIVOT COLUMN '----------------------> EXCEPT THE PIVOT ELEMENT For update_row = 1 To Vertical_Size_Tableau If update_row <> Pivot_row Then ' The previous values of the pivot column now being overwritten are needed ' more under OLD_VALUE_PIVOT_COLUMN[update_row] = Tableau[update_row][Pivot_column] Tableau[update_row][Pivot_column] = 0 EndIf EndFor '----------------------> UPDATE THE ROW For update_column = 1 To Horizontal_Size_Tableau Tableau[Pivot_row][update_column] = Tableau[Pivot_row][update_column] * RECIPROCAL_P_E_V EndFor For update_row = 1 To Vertical_Size_Tableau For update_column = 1 To Horizontal_Size_Tableau ' Here for any cell in the Tableau If update_column <> Pivot_column Then ' Here for any cell in the Tableau outside the PIVOT COLUMN If update_row <> Pivot_row Then ' Here for any non-zero cell in the Tableau outside the PIVOT COLUMN and the PIVOT ROW ' =================================================================== ' Explanations from IMSE Concept Library | Laurel Nichols & Gina Christofaro | Spring 2015 ' ------------------------------------------------------------------------------------------------------------------ ' In order to keep the tableau equivalent, the other variables not contained in the pivot column ' or pivot row must be calculated by using the new pivot values. For each new value, multiply ' the negative of the value in the old pivot column by the value in the new pivot row that ' corresponds to the value being calculated. Then add this to the old value from the old tableau ' to produce the new value for the new tableau. ' =================================================================== ' just for clarity, I store the current cell value in a variable Curr_cell_value = Tableau[update_row][update_column] ' the new values from the pivot row are readily available. I select the one corrresponding ' to the current column Value_new_pivot_row = Tableau[Pivot_row][update_column] ' the old values from the pivot column were saved beforehand. I select the one corrresponding ' to the current row, and change its sign Neg_value_old_pivot_column = OLD_VALUE_PIVOT_COLUMN[update_row] * -1 ' now the value for the new tableau cell can be assigned Tableau[update_row][update_column]=(Neg_value_old_pivot_column * Value_new_pivot_row) + Curr_cell_value EndIf EndIf EndFor EndFor TABLEAU_NUMBER = TABLEAU_NUMBER + 1 Goto BEGIN_SECOND_LOOP EXIT_SECOND_LOOP: ShowSimplexTableau() TextWindow.WriteLine(" ") TextWindow.WriteLine(" PHASE 2 COMPLETED - NO MORE NEGATIVE VALUES IN THE LAST ROW") TextWindow.WriteLine(" ") TextWindow.WriteLine(" ====> EXPECTED RESULTS <=====") TextWindow.WriteLine("Grams per bar, PEANUT BUTTER: Around 15") TextWindow.WriteLine("Grams per bar, OATS: Around 37") TextWindow.WriteLine("Grams per bar, DRIED CRANBERRIES: Around 15") TextWindow.WriteLine("COST PER BAR (cents): Around 15.7 cents") TextWindow.WriteLine("Grams, MINIMUM Protein content: 10") TextWindow.WriteLine("Grams, MAXIMUM Fat content: 14") TextWindow.WriteLine(" ") TextWindow.Read() TextWindow.WriteLine(" ====> ACTUAL RESULTS <=====") '====================================================== ' TABLEAU STRUCTURE '====================================================== 'Column Column Column Column Column Column Column ' 1 2 3 4 5 6 7 ' ' Peanut Oats Cran- S1 S2 (*) B ' Butter berries '====================================================== ' (*) - column of the value of the objective function ' B - the "Beta" column will contain optimal solutions for the basic variables '====================================================== ' Identify solutions '====================================================== '====================================================== ' FIND BASIC VARIABLES - those having a single 1 in their column and the ' rest is all zeros. The solution is in the last ("Beta") column, in the row that ' contains a 1 in the basic variable column '====================================================== For J = 1 to (Horizontal_Size_Tableau-1) Column_Total = 0 Count_Zero = 0 For I = 1 to Vertical_Size_Tableau Current_value = Tableau[I][J] Column_Total = Column_Total + Current_value If Current_value = 0 Then Count_Zero = Count_Zero + 1 EndIf If Current_value = 1 Then Here_Found_One = I EndIf EndFor If Count_Zero = (Vertical_Size_Tableau-1) Then If Column_Total = 1 Then RESULT_VALUE = Tableau[Here_Found_One][Horizontal_Size_Tableau] EndIf Else RESULT_VALUE = 0 EndIf Display_cell=math.Round(RESULT_VALUE*100)*RESULT_MULTIPLIER[J] Display_cell=Display_cell/100 SOLUTION[J]=Display_cell If SHOW_RESULT[J] = "True" Then TextWindow.WriteLine(COLUMN_FULL_NAME[J]+" = "+ Display_cell) EndIf EndFor ' ======================================= ' EXPLICITLY SHOW PROTEIN AND FAT CONTENT ' IN EACH BAR ' ======================================= For I = 1 to 2 TextWindow.Write(Constraint_description[I]) TextWindow.Write(" = ") TextWindow.Write(Constraint[I][4]) TextWindow.Write(" - ACTUAL CONTENT OF ONE BAR = ") ActualContent = 0 For J = 1 To 3 ' Divided by 10 - requirements are in grams, results are in 10 gram servings ActualContent=ActualContent+Constraint[I][J]*SOLUTION[J]/Serving_Size EndFor TextWindow.WriteLine(ActualContent) EndFor TextWindow.WriteLine("") TextWindow.WriteLine("Press any key to terminate the program") TextWindow.Read() Program.End() Sub ShowSimplexTableau TextWindow.Clear() TextWindow.WriteLine("=============================================================") TextWindow.WriteLine(" TABLEAU "+TABLEAU_NUMBER) TextWindow.WriteLine("=============================================================") For I = 1 To Vertical_Size_Tableau TextWindow.Write(STARRED[I]) TextWindow.Write(COLUMN_NAME[I+3]+" | ") For J = 1 To Horizontal_Size_Tableau Display_cell=math.Round(Tableau[I][J]*100) Display_cell=Display_cell/100 TextWindow.Write(" "+Display_cell+" | ") EndFor TextWindow.Write(CRLF) EndFor EndSub